package Graph.graphWithNoweight.dfs;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/5 17:34
 * @Version 1.0
 */
public class Path {

    private Graph G;
    private boolean[] visited;
    private int s;
    private int t;

    private int[] pre;

    private ArrayList<Integer> order = new ArrayList<>();

    public Path(Graph G,int s,int t){

        this.G = G;
        G.validateVertex(s);
        G.validateVertex(t);

        this.s = s;
        this.t = t;
        visited = new boolean[G.V()];
        //pre[i] == i之前的那个节点
        pre = new int[G.V()];

        for(int i=0;i<pre.length;i++){
            pre[i] = -1;
        }

        dfs(s,s);

        for(boolean e : visited){
            System.out.print(e+" ");
        }
        System.out.println();
    }

    //参数 t 为目标节点，，返回的是到t 的路径（这里是倒叙）
    public Iterable<Integer> path(){
        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo()){
            return res;
        }
        int cur = t;
        //倒叙 ，从后往前找的、
        while (cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    // 是否和 s 节点相连（如果遍历到了 那一定是想连的。）
    public boolean isConnectedTo(){
        G.validateVertex(t);
        return visited[t];
    }

    private void dfs(int v,int parent) {
        visited[v] = true;
        order.add(v);
        pre[v] = parent;
        for(int w:G.adj(v)){
            if(!visited[w]){
                dfs(w,v);
            }
        }
    }

    //虽然order 是ArrayList<Integer> 类型，但是这个类型实现了Iterable<Integer>接口
    public Iterable<Integer> order(){
        return order;
    }

    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        Path path = new Path(g,0,6);
        //求从0 到 6 的路径
        System.out.println("“0 - 6 路径” :"+path.path());

        Path path2 = new Path(g,0,7);
        //求从0 到 6 的路径
        System.out.println("“0 - 7 路径” :"+path2.path());

    }


}
